package main

import "fmt"

func quicksort(nums []int,lo int,hi int){
	if lo >= hi {
		return
	}
	
	p:=partition(nums,lo,hi)
	quicksort(nums,lo,p-1)
	quicksort(nums,p+1,hi)
}

// 快慢指针
func partition(nums []int,lo int,hi int)int{
	i:=lo-1
	for j := lo; j < hi; j++ {
		if nums[j]<nums[hi]{
			i++
			nums[i],nums[j] = nums[j],nums[i]
		}
	}
	
	nums[i+1],nums[hi] = nums[hi],nums[i+1]
	return i+1
}

func main(){
	nums:=[]int{3,6,2,1,6,9}
	quicksort(nums,0,len(nums)-1)
	fmt.Println(nums)
}